{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Maximum Number of String Pairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #string #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #字符串 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumNumberOfStringPairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大字符串配对数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的数组&nbsp;<code>words</code>&nbsp;，数组中包含 <strong>互不相同</strong>&nbsp;的字符串。</p>\n",
    "\n",
    "<p>如果字符串&nbsp;<code>words[i]</code>&nbsp;与字符串 <code>words[j]</code>&nbsp;满足以下条件，我们称它们可以匹配：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>字符串&nbsp;<code>words[i]</code>&nbsp;等于&nbsp;<code>words[j]</code>&nbsp;的反转字符串。</li>\n",
    "\t<li><code>0 &lt;= i &lt; j &lt; words.length</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回数组 <code>words</code>&nbsp;中的&nbsp;<strong>最大</strong>&nbsp;匹配数目。</p>\n",
    "\n",
    "<p>注意，每个字符串最多匹配一次。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>words = [\"cd\",\"ac\",\"dc\",\"ca\",\"zz\"]\n",
    "<b>输出：</b>2\n",
    "<strong>解释：</strong>在此示例中，我们可以通过以下方式匹配 2 对字符串：\n",
    "- 我们将第 0 个字符串与第 2 个字符串匹配，因为 word[0] 的反转字符串是 \"dc\" 并且等于 words[2]。\n",
    "- 我们将第 1 个字符串与第 3 个字符串匹配，因为 word[1] 的反转字符串是 \"ca\" 并且等于 words[3]。\n",
    "可以证明最多匹配数目是 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>words = [\"ab\",\"ba\",\"cc\"]\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>在此示例中，我们可以通过以下方式匹配 1 对字符串：\n",
    "- 我们将第 0 个字符串与第 1 个字符串匹配，因为 words[1] 的反转字符串 \"ab\" 与 words[0] 相等。\n",
    "可以证明最多匹配数目是 1 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>words = [\"aa\",\"ab\"]\n",
    "<b>输出：</b>0\n",
    "<strong>解释：</strong>这个例子中，无法匹配任何字符串。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= words.length &lt;= 50</code></li>\n",
    "\t<li><code>words[i].length == 2</code></li>\n",
    "\t<li><code>words</code>&nbsp;包含的字符串互不相同。</li>\n",
    "\t<li><code>words[i]</code>&nbsp;只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-maximum-number-of-string-pairs](https://leetcode.cn/problems/find-maximum-number-of-string-pairs/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-maximum-number-of-string-pairs](https://leetcode.cn/problems/find-maximum-number-of-string-pairs/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"cd\",\"ac\",\"dc\",\"ca\",\"zz\"]', '[\"ab\",\"ba\",\"cc\"]', '[\"aa\",\"ab\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumberOfStringPairs(self, words: List[str]) -> int:\n",
    "        the_others: Set[str] = set(words)\n",
    "        n_pairs: int = 0\n",
    "\n",
    "        for word in words:\n",
    "            the_others.discard(word)\n",
    "            rev: str = \"{:s}{:s}\".format(word[1], word[0])\n",
    "            if rev in the_others:\n",
    "                n_pairs += 1\n",
    "\n",
    "        return n_pairs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumberOfStringPairs(self, words: List[str]) -> int:\n",
    "        return sum(i == j[::-1] for i_index, i in enumerate(words) for j in words[i_index+1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumberOfStringPairs(self, words: List[str]) -> int:\n",
    "        ans = 0\n",
    "        for i in words:\n",
    "            if i[::-1] in words and i != i[::-1]:\n",
    "                ans += 1\n",
    "        return int(ans/2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumNumberOfStringPairs(self, words: List[str]) -> int:\n",
    "        sum=0\n",
    "        for i in words:\n",
    "            \n",
    "            m=i[::-1]\n",
    "            if m!=i:\n",
    "                if m in words:\n",
    "                    sum+=1\n",
    "            \n",
    "            \n",
    "                \n",
    "            \n",
    "            \n",
    "        return sum//2"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
